package com.zjw.zy.common;

import androidx.annotation.NonNull;

import java.util.ArrayList;
import java.util.Collection;

/**
 * @author ：zhong.jw
 * @date ：Created in 2022/11/9 17:10
 * <p>
 * 有序列表
 */
public class SortedList<T extends Comparable<T>> extends ArrayList<T> {

    public SortedList() {
        super();
    }


    public SortedList(Collection<? extends T> c) {
        super(c);
        sort(Comparable::compareTo);
    }

    @Override
    public boolean addAll(@NonNull Collection<? extends T> c) {
        boolean b = super.addAll(c);
        sort(Comparable::compareTo);
        return b;
    }

    @Override
    public boolean add(T t) {
        super.add(indexOfInsert(t), t);
        return true;
    }

    @Override
    public void add(int index, T element) {
        throw new UnsupportedOperationException("un support add(int index, T element) for SortedList");
    }

    @Override
    public T set(int index, T element) {
        throw new UnsupportedOperationException("un support set(int index, T element) for SortedList,please use set(T element)");
    }

    public void addIfAbsent(T t) {
        if (!contains(t)) {
            this.add(t);
        }
    }

    public void set(T element) {
        int index = indexOf(element);
        if (index >= 0) {
            super.set(index, element);
        }
    }

    @Override
    public boolean remove(Object o) {
        int index = indexOf(o);
        if (index >= 0) {
            super.remove(index);
            return true;
        }
        return false;
    }

    @Override
    public boolean contains(Object o) {
        return this.indexOf(o) >= 0;
    }

    @Override
    @SuppressWarnings("unchecked")
    public int indexOf(Object o) {
        T target = (T) o;
        int pl = 0;
        int pr = size() - 1;
        int middle;

        while (pl <= pr) {
            middle = (pl + pr) >>> 1;
            T item = get(middle);
            int cmp = item.compareTo(target);
            if (cmp > 0) {
                pr = middle - 1;
            } else if (cmp < 0) {
                pl = middle + 1;
            } else {
                return middle;
            }
        }
        return -1;
    }

    /**
     * 查找插入的index
     */
    private int indexOfInsert(T t) {
        final int size = size();
        int pl = 0;
        int pr = size - 1;
        int middle;
        while (pl <= pr) {
            middle = (pl + pr) >>> 1;
            T item = get(middle);
            int cmp = item.compareTo(t);
            //item > t
            if (cmp > 0) {
                if (middle - 1 >= 0 && get(middle - 1).compareTo(t) <= 0) {
                    return middle;
                }
                pr = middle - 1;
            } else if (cmp < 0) {
                //item < t
                if (middle + 1 < size && get(middle + 1).compareTo(t) >= 0) {
                    return middle + 1;
                }
                pl = middle + 1;
            } else {
                return middle;
            }
        }
        if (pl == 0) {
            return 0;
        } else {
            //last
            return size;
        }
    }
}

